package cn.yza.算法.排序算法;

/** 计数排序优化版
 *  将数组长度定为 max-min+1 ，即不仅要找出最大值，还要找出最小值
 *  根据两者的差来确定计数数组的长度
 * @author Honglixi
 * @create 2021-12-05 22:18
 */
public class CountSort02 {
    public int[] countSort(int[] A) {
        //找出数组A中的最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : A) {
             max = Math.max(max, num);
             min = Math.min(min, num);

        }
        //初始化计数数组count，长度为最大值减去最小值加1
        int[] count = new int[max - min + 1];
        //对计数数组各元素赋值
        for (int num : A) {
            //A中的元素要减去最小值，再做为新索引
            count[num - min]++;
        }
        //创建结果数组
        int[] result = new int[A.length];
        //创建结果数组的起始索引
        int index = 0;
        //遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[index++] = i + min;
                count[i]--;
            }
        }
        //返回结果数组
        return result;
    }
}
